package com.yeung.Divided;

public class 递归求数组最大值 {
    public static void main(String[] args) {
        int arr[] = new int[]{3, 4, 1, 53, 21, 57, 21};
        int max = getMax(arr, 0);
//        System.out.println(max);
        System.out.println(getSum(new int[]{1, 2, 3, 4}, 0, 3));
    }

    /**
     * 递归求数组最大值
     *
     * @param arr 目标数组
     * @param i   起始下标
     * @return
     */
    private static int getMax(int[] arr, int i) {
        if (i == arr.length - 1) {
            return arr[i];//只有一个元素的时候,它就是最大值（特定问题的解）
        } else {
            //假设解出了子问题i+1的最大值,
            //将i+1的最大值和当前i进行比较, 返回最大的
            //将最后一个元素与“假设存在的”最大值比较
            int max = Math.max(arr[i], getMax(arr, i + 1));
            return max;
        }


    }

    /**
     * 分治方法求数组最大和
     *
     *
     * @param arr
     * @param low
     * @param high
     * @return
     */
    private static int getSum(int[] arr, int low, int high) {
        if (low >= high) return arr[high];// “治” 直接求解
        int mid = (low + high) / 2;// “分” 分解成两个子问题
        // “合” 自底向上求子数组l和r的和
        return getSum(arr, low, mid) + getSum(arr, mid + 1, high);
    }


}
